package BinarySearch;

import java.util.Arrays;

public class BinarySearch {
  public static void main(String[] args) {
    int arr[] = { 2, 33, 45, 48, 51, 66, 77, 99 };

    BinarySearchBasic test1 = new BinarySearchBasic();
    System.out.println(test1.fn(arr, 33));
    System.out.println(test1.fn(arr, 45));
    System.out.println(test1.fn(arr, 48));
    System.out.println(test1.fn(arr, 40));
    System.out.println(test1.fn(arr, 47));

    // BinarySearchAlternative test2 = new BinarySearchAlternative();
    // System.out.println(test2.fn(arr, 48));
    // System.out.println(test2.fn(arr, 45));
    // System.out.println(test2.fn(arr, 33));
    // System.out.println(test2.fn(arr, 40));
    // System.out.println(test2.fn(arr, 47));

    // BinarySearchBalance test3 = new BinarySearchBalance();
    //  System.out.println(test3.fn(arr, 48));
    // System.out.println(test3.fn(arr, 45));
    // System.out.println(test3.fn(arr, 33));
    // System.out.println(test3.fn(arr, 40));
    // System.out.println(test3.fn(arr, 47));

    int index = test1.fn(arr, 40);
    System.out.println(index); // -3

    // 如果没找到, 则插入target
    if (index < 0) {
      int insertIndex = Math.abs(index + 1);

      int newArr[] = new int[arr.length + 1];
      //              旧数组 起始下标  新数组  起始下标     插入元素个数
      System.arraycopy(arr, 0, newArr, 0, insertIndex);
      // [2, 33, 0, 0, 0, 0, 0, 0, 0]
      newArr[insertIndex] = 40;
      // [2, 33, 40, 0, 0, 0, 0, 0, 0]
      System.arraycopy(arr, insertIndex, newArr, insertIndex + 1, arr.length - insertIndex);
      // [2, 33, 40, 45, 48, 51, 66, 77, 99]
      System.out.println("新数组: " + Arrays.toString(newArr));
    }
  }
}
